Masala #1124

Xotira 32 MB Vaqt 1000 ms Qiyinchiligi 18 %

#Prefix Sum

#Suffix Array

#Two Pointers

#Tartiblash

3.4 (Baholar 14)

Maximum sum

Sizga uzunligi $N$ ga teng bo'lgan $a_1, a_2, a_3, ..., a_N$ massiv berilgan. Siz bu massiv ustida $K$ ta amal bajarishingiz kerak. Natijada hosil bo'lgan massiv summasi maximal bo'lib qolsin.

bitta amal bilan siz massivdagi eng kichik 2ta elementni o'chirishingiz mumkin.
bitta amal bilan massivdagi eng katta 1ta elementni o'chirishingiz mumkin.

Eslatma: amallani o'zingiz tanlaysiz.

Kiruvchi ma'lumotlar:

Kirish faylining birinchi qatorida ikkita butun son $N,K$ $(3\le N \le 2*10^5; 1\le K \le 99999 ; 2K \le N-1)$ kiritiladi.
Ikkinchi qatorda $a_i$ $(1\le a_i \le 10^9)$ massiv elementlari kiritiladi.

Chiquvchi ma'lumotlar:

Chiqish faylida $K$ ta amal bajarilgandan keyingi massivning maximal summasini chiqaring.

Misollar

#	input.txt	output.txt
1	5 1 2 5 1 10 6	21
2	5 2 2 5 1 10 6	11
3	6 1 15 22 12 10 13 11	62
4	6 2 15 22 12 10 13 11	46

Telegram Facebook

Yechimini yuborish

Bu amalni bajarish uchun tizimga kiring, agar profilingiz bo'lmasa istalgan payt ro'yxatdan o'tishingiz mumkin